package dp;

import java.util.Scanner;

//给定一个序列和m，求最大的m段不相交的连续子序列之和
public class MSubOrderProblem {

	public static void main(String[] args) {
		Scanner scanner=new Scanner(System.in);
		while(scanner.hasNext()){
		int m=scanner.nextInt();  //分成m段
		int arrayLength=scanner.nextInt();   //获取输入的序列长度
		int[] number=new int[arrayLength];   //用以存储动态规划中的结果
		for(int i=0;i<arrayLength;i++){
			number[i]=scanner.nextInt();
		}
		getMaxSum(number,m);
		}
		scanner.close();
	}

	public static void getMaxSum(int[] number, int m) {
		int length=number.length;
		if(length<m||m<1) {
			System.err.println("您输入的数据有误");
			return;  
		}
		int maxSum=0;  //定义最大和
		//sum[i][j]表示前j项中i个子段的最大和,其中由于子段的数目必须小于等于前j项中数字的数目，即i<=j
		//sum[i][j]=max{ sum[i-1][t]+a[j],sum[i][j-1]+a[j] } 其中i-1<=t<j
		int[][] sum=new int[m+1][number.length+1];   //用以存储动态规划中的结果
		//sum[1][length]=HD1003.getMaxNum(number);
		for(int i=1;i<=m;i++){
			/*for (int j = i; j <=length; j++) {
				int max=sum[i-1][i-1];
				for (int k = i-1; k <j; k++) {
					//首先找到t从i-1到j-1中最大的sum
					if(sum[i-1][k]>max){
						max=sum[i-1][k];
					}
					sum[i][j]= Math.max(max+number[j-1], sum[i][j-1]+number[j-1]);
//					System.out.println("i"+i+"j"+j+sum[i][j]);
				}
			}*/
			//n-m+i限制避免多余运算，当i=m时，j最大为n，可据此递推所有情形  
	        for(int j=i; j<=length-m+i; j++)  
	        {  
	            if(j>i)  
	            {  
	                sum[i][j] = sum[i][j-1] + number[j-1];//代表a[j]同a[j-1]一起，都在最后一子段中  
	                for(int k=i-1; k<j; k++)  
	                {  
	                    if(sum[i][j]<sum[i-1][k]+number[j-1])  
	                        sum[i][j] = sum[i-1][k]+number[j-1];//代表最后一子段仅包含a[j]  
	                }  
	            }  
	           /* else  
	            {  
	                sum[i][j] = sum[i-1][j-1]+number[j-1];//当i=j时，每一项为一子段  
	            }  */
		}
		}
		for (int i=m;i<sum[m].length;i++) {
			if(maxSum<sum[m][i])  
				maxSum=sum[m][i]; 
		}
		System.out.println(maxSum);
	}
}
